package mo.tags.greedy;

import java.util.HashMap;
import java.util.Map;

public class L659 {

    public boolean isPossible(int[] nums) {
        Map<Integer, Integer> countMap = new HashMap<>();
        Map<Integer, Integer> endMap = new HashMap<>();
        for (int x : nums) {
            countMap.put(x, countMap.getOrDefault(x, 0)+1);
        }
        for (int x : nums) {
            int count = countMap.getOrDefault(x, 0);
            if (count > 0) {
                int preEndCount = endMap.getOrDefault(x - 1, 0);
                if (preEndCount > 0) {
                    countMap.put(x, count-1);
                    endMap.put(x-1, preEndCount-1);
                    endMap.put(x, endMap.getOrDefault(x, 0)+1);
                } else {
                    int count1 = countMap.getOrDefault(x+1, 0);
                    int count2 = countMap.getOrDefault(x+2, 0);
                    if (count1 > 0 && count2 > 0) {
                        countMap.put(x, count - 1);
                        countMap.put(x + 1, count1 - 1);
                        countMap.put(x + 2, count2 - 1);
                        endMap.put(x+2, endMap.getOrDefault(x+2, 0)+1);
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        L659 test = new L659();
        System.out.println(test.isPossible(new int[]{1,2,3,4,6,7,8,9,10,11}));
    }
}
